package com.zjsru.oneDay202209;


import java.util.Arrays;

/**
 * @Author: likew
 * @Date: 2022/9/12
 *  特殊数组的特征值
 *
 * 输入：nums = [3,5]
 * 输出：2
 * 解释：有 2 个元素（3 和 5）大于或等于 2 。
 *
 * 输入：nums = [0,0]
 * 输出：-1
 * 解释：没有满足题目要求的特殊数组，故而也不存在特征值 x 。
 * 如果 x = 0，应该有 0 个元素 >= x，但实际有 2 个。
 * 如果 x = 1，应该有 1 个元素 >= x，但实际有 0 个。
 * 如果 x = 2，应该有 2 个元素 >= x，但实际有 0 个。
 * x 不能取更大的值，因为 nums 中只有两个元素。
 *
 *
 */
public class SpecialArray {
    /**
     * 二分
     * */
    public int specialArray(int[] nums) {
        int len = nums.length;
        int right = 0;
        for (int num : nums) {
            right = Math.max(right, num);
        }
        int left = 1;
        right = Math.min(right, len);
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            int bigger = check(nums, mid);
            if (bigger == mid) {
                return mid;
            } else if (bigger > mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
    /**
     * 获取比中位数大的数字个数,
     * 如果相同时即找到特殊值了， 如果大于mid，代表特殊值还是不够多。
     * */
    private int check(int[] nums, int mid) {
        int n = nums.length;
        int cnt = 0;
        for (int num : nums) {
            if (num >= mid) {
                cnt++;
            }
        }
        return cnt;
    }
    
    /**
     * 排序 + 枚举 + 二分
     */
    public int specialArray2(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        for (int x = 0; x < 1010; x++) {
            int left = 0, right = len - 1;
            while (left < right) {
                int mid = (left + right) >> 1;
                if (nums[mid] >= x) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            //对x的校验，len - right 即是 len - mid的值，数组中超过x的验证x即为特殊值
            if (nums[right] > x && x == len - right) {
                return x;
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        SpecialArray specialArray = new SpecialArray();
        int[] nums = new int[]{3,6,7,7,0};
        System.out.println(specialArray.specialArray2(nums));
    }
}
